#include <iostream>
#include <queue>
#include <unordered_map>
#include <functional>
using namespace std;

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;

        for (int i = 0; i < k; i++)
        {
            pq.push(nums[i]);
        }

        for (int i = k; i < nums.size(); i++)
        {
            if (pq.top() < nums[i])
            {
                pq.pop();
                pq.push(nums[i]);
            }
        }

        return pq.top();
    }
};

class Solution {
    struct Greater
    {
        bool operator()(const pair<int, int>& p1, const pair<int, int>& p2)
        {
            return p1.second > p2.second;
        }
    };

public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for (auto e : nums)
        {
            hash[e]++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, Greater> pq;
        for (auto& e : hash)
        {
            if (pq.size() < k)
            {
                pq.push(e);
            }
            else
            {
                if (pq.top().second < e.second)
                {
                    pq.pop();
                    pq.push(e);
                }
            }
        }
        vector<int> ret;
        while (!pq.empty())
        {
            ret.push_back(pq.top().first);
            pq.pop();
        }
        return ret;
    }
};

class MedianFinder {
public:
    priority_queue<int> queMin;
    priority_queue<int, vector<int>, greater<int>> queMax;
    MedianFinder()
    {

    }

    void addNum(int num)
    {
        if (queMin.empty() || num <= queMin.top()) {
            queMin.push(num);
            if (queMax.size() + 1 < queMin.size()) {
                queMax.push(queMin.top());
                queMin.pop();
            }
        }
        else {
            queMax.push(num);
            if (queMax.size() > queMin.size()) {
                queMin.push(queMax.top());
                queMax.pop();
            }
        }

    }

    double findMedian()
    {
        if (queMin.size() > queMax.size()) {
            return queMin.top();
        }
        return (queMin.top() + queMax.top()) / 2.0;

    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

class MedianFinder {
public:

    priority_queue<int, vector<int>, greater<int>> high;
    priority_queue<int> low;
    int l = 0, r = 0;

    MedianFinder() {

    }

    void addNum(int num)
    {
        low.push(num), l++;

        if (l && r)
            while (low.top() > high.top())
            {
                high.push(low.top());
                low.pop();
                l--, r++;
            }


        while ((l - r) > 1)
        {
            high.push(low.top());
            low.pop();
            l--, r++;
        }

        while ((r - l) > 1)
        {
            low.push(high.top());
            high.pop();
            l++, r--;
        }
    }

    double findMedian()
    {
        if (l == r)
        {
            return (double)(low.top() + high.top()) / 2;
        }
        else if (l > r)
        {
            return low.top();
        }
        else
        {
            return high.top();
        }
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

int main()
{

	return 0;
}